class Solution {
public:
    class Trie{
    public:
        unordered_map<char,Trie*> next;
        bool isEnd;
        Trie():isEnd(false){}
        
        void insert(string s){
            Trie* node = this;
            for(char e : s){
                if(!node->next.count(e)){
                    node->next[e] = new Trie();
                }
                node = node->next[e];
            }
            node->isEnd = true;
        }
        
        bool search(string s){
            Trie* node = this;
            for(char e : s){
                if(node->next[e]->isEnd == false){
                    return false;
                }
                node = node->next[e];
            }
            return true;
        }
    };
    string longestWord(vector<string>& words) {
        Trie* root = new Trie();
        for(string& s : words){
            root->insert(s);
        }
        string ret = "";
        for(string& s : words){
            if(root->search(s) && (s.size() > ret.size() || s.size() == ret.size() && s < ret)){
                ret = s;
            }
        }
        return ret;
    }
};
